<head>
    <meta charset="UTF-8">
<title>算法训练 Dima and Game</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>Dima和Anya喜欢玩各种游戏。现在Dima想出了一个新游戏想和Anya玩。</div>
<div>&nbsp;</div>
<div>Dima在纸上写下n对整数(l[i],r[i])(1&lt;=l[i]&lt;r[i]&lt;=p)。然后玩家轮流进行操作。轮到自己时，可以进行下面的操作：</div>
<div>1.选择第i对数(1&lt;=i&lt;=n)，满足r[i]-l[i]&gt;2;</div>
<div>2.将第i对数替换为( l[i]+floor((r[i]-l[i])/3) , l[i]+2*floor((r[i]-l[i])/3) )或者( l[i] , r[i]-floor((r[i]-l[i])/3) )。floor(x)表示向下取整。</div>
<div>&nbsp;</div>
<div>不能进行操作的玩家则输。</div>
<div>&nbsp;</div>
<div>当然，Dima希望先进行操作的Anya赢得游戏。所以Dima需要写下这样的n对整数(l[i],r[i])(1&lt;=l[i]&lt;r[i]&lt;=p)，使得如果两个玩家都采取最优策略，先操作的玩家取得胜利。请计算Dima有多少种这样的方法。输出方案数模1000000007(10^9+7)后的值。</div>
<div>&nbsp;</div>
<div>如果这些数对被按照不同的顺序写了下来，则将其视作不同的方法。</div>
<p>【输入格式】<br />
第一行包含两个空格隔开的整数n,p。<br />
【输出格式】<br />
输出一行包含答案模1000000007(10^9+7)后的值。<br />
【样例输入】<br />
2 2<br />
【样例输出】<br />
0</p>
<p>【样例输入】<br />
4 4<br />
【样例输出】<br />
520<br />
<br />
【样例输入】<br />
100 1000<br />
【样例输出】<br />
269568947<br />
【数据规模和约定】<br />
对于20%的数据，1&lt;=n&lt;=10,1&lt;=p&lt;=10；<br />
对于100%的数据，1&lt;=n&lt;=1000,1&lt;=p&lt;=10^9。</p>